package bishiqiangxun;
import java.util.*;
public class Test3 {
    //题目: day29 第三题 最长上升子序列 (二)
    //两种做法 :动态规划  或者  贪心+二分查找
    public static void main(String[] args) {

    }
    //动态规划
    public int LIS (int[] a) {
        // write code here
        //动态规划
        int n = a.length;
        if(n == 0) return 0;
        //创建一个dp数组
        int[] dp = new int[n];
        //dp数组表示当前下标的最长上升子序列
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(a[j] < a[i]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //Arrays.sort(dp);  不能排序 不然会超时

        int len =  Arrays.stream(dp).max().getAsInt();
        return len;
    }

    //贪心+二分查找
    public int LIS1 (int[] a) {
        // write code here
        //贪心+二分
        int n = a.length;
        //用一个数组存 当前下标最小的末尾
        int[] arr = new int[n+1];
        int ret = 0;  //这个表示当前找的下标
        for(int x : a) {
            if(ret == 0  || x > arr[ret]) {
                arr[++ret] = x;
            }else {

                //二分查找
                int left =1;
                int right = ret;
                while(left < right) {
                    int mid = left+(right-left) /2;
                    if(x <= arr[mid]) {
                        right = mid;
                    }else {
                        left = mid+1;
                    }

                }
                arr[left] = x;
            }
        }
        return ret;
    }
}
